/**
  @(#)$Id: AL_ListCircularDouble.h 74 2013-10-10 12:42:07Z xiaoting $
  @brief    Double-way circular list is another form of one-way linked list structure, which is characterized by a pointer to the list 
  of the last one is no longer a null value, but point to the head of the linked list. So long as we know any node in the linked list 
  can be found circulating list of all other nodes.
  
			Also called double-linked list doubly linked list is a list in which each data node in both two pointers that point to a 
  direct successor and direct precursors. Therefore, two-way linked list from any one of the node point, can easily access its 
  predecessor and successor nodes node.

  @Author $Author: xiaoting $
  @Date $Date: 2013-10-10 20:42:07 +0800 (周四, 10 十月 2013) $
  @Revision $Revision: 74 $
  @URL $URL: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_ListCircularDouble.h $
  @Header $Header: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_ListCircularDouble.h 74 2013-10-10 12:42:07Z xiaoting $
 */

#ifndef CXX_AL_LISTCIRCULARDOUBLE_H
#define CXX_AL_LISTCIRCULARDOUBLE_H

#ifndef CXX_AL_NODE_H
#include "AL_Node.h"
#endif

///////////////////////////////////////////////////////////////////////////
//			AL_ListCircularDouble
///////////////////////////////////////////////////////////////////////////

template<typename T> 
class AL_ListCircularDouble
{
public:
	static const DWORD LISTDOUBLE_POSITION_INVALID		= 0xffffffff;
	/**
	* Construction
	*
	* @param
	* @return
	* @note
	* @attention
	*/
	AL_ListCircularDouble();

	/**
	* Destruction
	*
	* @param
	* @return
	* @note
	* @attention
	*/
	~AL_ListCircularDouble();

	/**
	* Length
	*
	* @param VOID
	* @return DWORD
	* @note get the length of the list
	* @attention
	*/
	DWORD Length() const;
	
	/**
	* Find
	*
	* @param const T& tData <IN>
	* @return DWORD
	* @note find the position of tData 
	* @attention  if not find, will be return 0xffffffff
	*/
	DWORD Find(const T& tData ) const;

	/**
	* IsElement
	*
	* @param const T& tData <IN>
	* @return BOOL
	* @note the tData  is in the list?
	* @attention
	*/
	BOOL IsElement(const T& tData ) const;

	/**
	* Insert
	*
	* @param DWORD dwIndex <IN>
	* @param const T& tData <IN> 
	* @return BOOL
	* @note inset the tData  into the list at the position
	* @attention
	*/
	BOOL Insert(DWORD dwIndex,const T& tData);

	/**
	* InsertBegin
	*
	* @param const T& tData <IN>
	* @return BOOL
	* @note inset the tData  into the list at the position
	* @attention
	*/
	BOOL InsertBegin(const T& tData);


	/**
	* InsertEnd
	*
	* @param const T& tData <IN>
	* @return BOOL
	* @note inset the tData  into the list at the position
	* @attention
	*/
	BOOL InsertEnd(const T& tData);

	/**
	* Remove
	*
	* @param const T& tData <IN>
	* @return BOOL
	* @note remove the tData in the list
	* @attention
	*/
	BOOL Remove(const T& tData);

	/**
	* RemoveAt
	*
	* @DWORD dwIndex <IN> 
	* @return BOOL
	* @note remove the tData in the list at the index (dwIndex)
	* @attention
	*/
	BOOL RemoveAt(DWORD dwIndex);

	/**
	* IsEmpty
	*
	* @param VOID
	* @return BOOL
	* @note the list has data?
	* @attention
	*/
	BOOL IsEmpty() const;

	/**
	* Get
	*
	* @param	T& tTypeOut <OUT>
	* @param	DWORD dwIndex <IN>
	* @return BOOL
	* @note get the T at the position
	* @attention the dwIndex must is little than the list length
	*/
	BOOL Get(DWORD dwIndex, T& tTypeOut) const;

	/**
	* Set
	* @param	T& tTypeOut <OUT>
	* @param	DWORD dwIndex <IN>
	* @param	const T& tData <IN>
	* @return BOOL
	* @note Replaced with the element element element on position index, and returns the old element...
	* @attention Index must in the list
	*/
	BOOL Set(DWORD dwIndex, const T& tData, T& tTypeOut);

	/**
	* Clear
	*
	* @param VOID
	* @return VOID
	* @note clear the data in the list
	* @attention all data will be clear
	*/
	VOID Clear();

protected:
private:
	/**
	* GetNodeByIndex
	*
	* @param DWORD dwIndex <IN>
	* @return AL_Node<T>*
	* @note get the const T& at the position
	* @attention the dwIndex must is little than the list length
	*/
	AL_Node<T>* GetNodeByIndex(DWORD dwIndex) const;

	/**
	*Copy Construct
	*
	* @param const AL_ListCircularDouble<T>& cAL_ListCircularDouble
	* @return
	*/
	AL_ListCircularDouble(const AL_ListCircularDouble<T>& cAL_ListCircularDouble);

	/**
	*Assignment
	*
	* @param const AL_ListCircularDouble<T>& cAL_ListCircularDouble
	* @return AL_ListCircularDouble<T>&
	*/
	AL_ListCircularDouble<T>& operator = (const AL_ListCircularDouble<T>& cAL_ListCircularDouble);

public:
protected:
private: 
	AL_Node<T>*		m_pHeader;
	DWORD			m_dwSize;
};

///////////////////////////////////////////////////////////////////////////
//			AL_ListCircularDouble
///////////////////////////////////////////////////////////////////////////
/**
* Construction
*
* @param
* @return
* @note
* @attention
*/
template<typename T> 
AL_ListCircularDouble<T>::AL_ListCircularDouble():
m_pHeader(NULL),
m_dwSize(0X00)
{
	m_pHeader = new AL_Node<T>;
	m_pHeader->m_pPre = m_pHeader;
	m_pHeader->m_pNext = m_pHeader;
}

/**
* Destruction
*
* @param
* @return
* @note
* @attention
*/
template<typename T> 
AL_ListCircularDouble<T>::~AL_ListCircularDouble()
{
	Clear();
	//delete the header
	if (NULL != m_pHeader) {
		delete m_pHeader;
		m_pHeader = NULL;
	}
}

/**
* Length
*
* @param
* @return DWORD
* @note get the length of the list
* @attention
*/
template<typename T> DWORD 
AL_ListCircularDouble<T>::Length() const
{
	return m_dwSize;
	/*
	if (TRUE == IsEmpty()) {
		return 0;
	}
	AL_Node<T>* pMove = NULL;
	DWORD dwCount = 1;

	pMove = m_pHeader->m_pNext;
	while (m_pHeader != pMove->m_pNext) {
		dwCount ++;
		pMove = pMove->m_pNext;
	}
	return dwCount;
	*/
}

/**
* Find
*
* @param const T& tData <IN>
* @return DWORD
* @note find the position of tData 
* @attention  if not find, will be return 0xffffffff
*/
template<typename T> DWORD 
AL_ListCircularDouble<T>::Find(const T& tData ) const
{
	if (TRUE == IsEmpty()) {
		return LISTDOUBLE_POSITION_INVALID;
	}
	
	AL_Node<T>* pMove = NULL;
	DWORD dwCount = 1;

	//loop the next data;
	pMove = m_pHeader->m_pNext;
	while (m_pHeader != pMove->m_pNext) {
		if (tData == pMove->m_tData) {
			//find the data
			return dwCount-1;
		}
		dwCount ++;
		pMove = pMove->m_pNext;
	}
	
	//the end
	if (tData == pMove->m_tData) {
		//find the data
		return dwCount-1;
	}

	return LISTDOUBLE_POSITION_INVALID;
}

/**
* IsElement
*
* @param const T& tData <IN> 
* @return BOOL
* @note the tData  is in the list?
* @attention
*/
template<typename T> BOOL 
AL_ListCircularDouble<T>::IsElement(const T& tData ) const
{
	if (LISTDOUBLE_POSITION_INVALID == Find(tData )) {
		return FALSE;
	}

	return TRUE;
}

/**
* Insert
*
* @param DWORD dwIndex <IN>
* @param const T& tData <IN> 
* @return BOOL
* @note inset the tData  into the list at the position
* @attention
*/
template<typename T> BOOL 
AL_ListCircularDouble<T>::Insert(DWORD dwIndex, const T& tData )
{
	if (dwIndex > Length()) {
		//can not insert to this position
		return FALSE;
	}
	AL_Node<T>* pInsert = new AL_Node<T>;
	pInsert->m_tData = tData;
	
	AL_Node<T>* pPre = NULL;
	//get the previous Node
	if (0x00 == dwIndex) {
		pPre = m_pHeader;
	}
	else {
		pPre = GetNodeByIndex(dwIndex - 1);
	}
	
	if ((NULL == pPre)) {
		//error
		return FALSE;
	}
	if (Length() == dwIndex){
		//end
		pPre->m_pNext = pInsert;
		pInsert->m_pPre = pPre;

		pInsert->m_pNext = m_pHeader;
		m_pHeader->m_pPre = pInsert;
	}
	else {
		//among of the list
		AL_Node<T>* pIndexNode = pPre->m_pNext;
		if ((NULL == pIndexNode)) {
			//error
			return FALSE;
		}
		pInsert->m_pNext = pIndexNode;
		pIndexNode->m_pPre = pInsert;

		pPre->m_pNext = pInsert;
		pInsert->m_pPre = pPre;
	}

	m_dwSize++;
	return TRUE;
}

/**
* InsertBegin
*
* @param const T& tData <IN> 
* @return BOOL
* @note inset the tData  into the list at the position
* @attention
*/
template<typename T> BOOL 
AL_ListCircularDouble<T>::InsertBegin(const T& tData )
{
	return Insert(0, tData);
}

/**
* InsertEnd
*
* @param const T& tData <IN> 
* @return BOOL
* @note inset the tData  into the list at the position
* @attention
*/
template<typename T> BOOL 
AL_ListCircularDouble<T>::InsertEnd(const T& tData )
{
	return Insert(Length(), tData);
}


/**
* Remove
*
* @param const T& tData <IN> 
* @return BOOL
* @note remove the tData in the list
* @attention
*/
template<typename T> BOOL 
AL_ListCircularDouble<T>::Remove(const T& tData )
{
	if (TRUE == IsEmpty()) {
		return FALSE;
	}

	BOOL bRemove = FALSE;
	AL_Node<T>* pMove = NULL;
	DWORD dwCount = 1;

	//loop the next data;
	pMove = m_pHeader->m_pNext;
	while (m_pHeader != pMove->m_pNext) {
		if (tData == pMove->m_tData) {
			pMove = pMove->m_pNext;
			//find the data
			bRemove = RemoveAt(dwCount-1);
			if (FALSE == bRemove) {
				return bRemove;
			}
		}
		else {
			pMove = pMove->m_pNext;
		}
		dwCount ++;
	}

	//the end
	if (tData == pMove->m_tData) {
		//find the data
		bRemove = RemoveAt(dwCount-1);
		if (FALSE == bRemove) {
			return bRemove;
		}
	}

	return bRemove;
}

/**
* RemoveAt
*
* @param DWORD dwIndex <IN> 
* @return BOOL
* @note remove the tData in the list at the index (dwIndex)
* @attention
*/
template<typename T> BOOL 
AL_ListCircularDouble<T>::RemoveAt(DWORD dwIndex)
{
	if (dwIndex > Length()) {
		//can not insert to this position
		return FALSE;
	}

	AL_Node<T>* pDelete = GetNodeByIndex(dwIndex);
	if (NULL == pDelete) {
		//error
		return FALSE;
	}

	AL_Node<T>* pPre = NULL;
	//get the previous Node
	if (0x00 == dwIndex) {
		pPre = m_pHeader;
	}
	else {
		pPre = pDelete->m_pPre;
	}

	if (NULL == pPre) {
		//error
		return FALSE;
	}
	pPre->m_pNext = pDelete->m_pNext;

	AL_Node<T>* pNext = pDelete->m_pNext;
	if (NULL != pNext) {
		//among of the list
		pNext->m_pPre = pPre;
	}

	delete pDelete;
	pDelete = NULL;

	m_dwSize--;
	return TRUE;
}

/**
* IsEmpty
*
* @param
* @return BOOL
* @note the list has data?
* @attention
*/
template<typename T> BOOL 
AL_ListCircularDouble<T>::IsEmpty() const
{
	return (m_pHeader == m_pHeader->m_pNext) ? TRUE:FALSE;
}

/**
* Get
*
* @param	T& tTypeOut <OUT>
* @param	DWORD dwIndex <IN>
* @return BOOL
* @note get the T at the position
* @attention the dwIndex must is little than the list length
*/
template<typename T> BOOL
AL_ListCircularDouble<T>::Get(DWORD dwIndex, T& tTypeOut) const
{
	if (TRUE == IsEmpty()) {
		//error
		return FALSE;
	}

	if (Length()-1 < dwIndex) {
		//error
		return FALSE;
	}
	
	AL_Node<T>* pGet = GetNodeByIndex(dwIndex);
	if (NULL == pGet) {
		//error
		return FALSE;
	}
	tTypeOut = pGet->m_tData;
	return TRUE;

	/* //test code
	if (TRUE == IsEmpty()) {
		//error
		return FALSE;
	}

	if (Length()-1 < dwIndex) {
		//error
		return FALSE;
	}

	AL_Node<T>* pGet = GetNodeByIndex(dwIndex);
	if (NULL == pGet) {
		//error
		return FALSE;
	}

	AL_Node<T>* pStop = pGet;
	while(pStop != pGet->m_pNext) {
		if (pStop == pGet) {
			//header no data
		}
		pGet = pGet->m_pNext;
	}
	return TRUE;
	*/
}

/**
* Set
* @param	DWORD dwIndex <IN>
* @param	const T& tData <IN>
* @param	T& tTypeOut <OUT>
* @return BOOL
* @note Replaced with the element element element on position index, and returns the old element...
* @attention Index must in the list
*/
template<typename T> BOOL 
AL_ListCircularDouble<T>::Set(DWORD dwIndex, const T& tData, T& tTypeOut)
{
	if (Length()-1 < dwIndex) {
		//error
		return FALSE;
	}
	
	AL_Node<T>* pSet = GetNodeByIndex(dwIndex);
	if (NULL == pSet) {
		//error
		return FALSE;
	}
	
	tTypeOut = pSet->m_tData;
	pSet->m_tData = tData;
	return TRUE;
}

/**
* Clear
*
* @param VOID
* @return VOID
* @note clear the data in the list
* @attention all data will be clear
*/
template<typename T> VOID 
AL_ListCircularDouble<T>::Clear()
{
	if (TRUE == IsEmpty()) {
		//No data,
		return;
	}

	AL_Node<T>* pDelete = NULL;
	while(m_pHeader != m_pHeader->m_pNext){
		//get the node
		pDelete = m_pHeader->m_pNext;
		m_pHeader->m_pNext = pDelete->m_pNext;
		delete pDelete;
		pDelete = NULL;
	}
	m_dwSize = 0x00;
}

/**
* GetNodeByIndex
*
* @param DWORD dwIndex <IN>
* @return AL_Node<T>* 
* @note get the const T& at the position
* @attention the dwIndex must is little than the list length
*/
template<typename T> AL_Node<T>* 
AL_ListCircularDouble<T>::GetNodeByIndex(DWORD dwIndex) const
{
	if (Length()-1 < dwIndex) {
		//error
		return NULL;
	}

	AL_Node<T>* pMove = NULL;
	DWORD dwCount = 1;
	//loop the next data;
	pMove = m_pHeader->m_pNext;
	while (m_pHeader != pMove->m_pNext) {
		if (dwCount-1 == dwIndex) {
			//get this place
			return pMove;
		}
		dwCount ++;
		pMove = pMove->m_pNext;
	}
	
	//the end
	return pMove;

	/* //test code
	//forward loop (only for test)
	//get the end node
	AL_Node<T>* pEnd = NULL;
	pEnd = m_pHeader->m_pPre;

	DWORD dwCount = Length();
	//loop the next data;
	AL_Node<T>* pMove = NULL;
	pMove = pEnd;
	while (m_pHeader != pMove->m_pPre) {
		if (dwCount-1 == dwIndex) {
			//get this place
			return pMove;
		}
		dwCount --;
		pMove = pMove->m_pPre;
	}

	//the end
	return pMove;
	*/
}

#endif // CXX_AL_LISTCIRCULARDOUBLE_H
/* EOF */
